package class_0923dynamicprogram;

import java.util.Arrays;

public class MinCostTickets {
    private static int[] durations = {1,7,30};
    private static int process(int[] days, int[] costs, int i){
        if(i==days.length){
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for(int k=0;k<3;k++){
            int j = i;
            while(j<days.length && days[j]<days[i]+durations[k]){
                j++;
            }
            //更新
            ans = Math.min(ans, costs[k] + process(days, costs, j));
        }
        return ans;
    }
    public static int mincostTickets(int[] days, int[] costs) {
        return process(days, costs, 0);
    }
    private static int process(int[] days, int[] costs, int i, int[] dp){
        if(i==days.length){
            return 0;
        }
        if(dp[i]!=Integer.MAX_VALUE){
            return dp[i];//先前算过， 直接算值。
        }
        int ans = Integer.MAX_VALUE;
        for(int k=0;k<3;k++){
            int j = i;
            while(j<days.length && days[j]<days[i]+durations[k]){
                j++;
            }
            ans = Math.min(ans, costs[k] + process(days, costs, j, dp));
        }
        //ans已经是i目前最小情况了。
        dp[i] = ans;// 写入缓存表中。
        return ans;
    }
    public static int mincostTickets2(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        return process(days, costs, 0, dp);
    }

    //
    public static int MAXN = 366;

    public static int[] dp = new int[MAXN];
    public static int mincostTickets3(int[] days, int[] costs) {
        int n = days.length;
        Arrays.fill(dp, 0,n+1,Integer.MAX_VALUE);
        dp[n] = 0;
        for (int i = n-1; i >= 0; i--) {
            for(int k=0;k<3;k++){
                int j = i;
                while(j<days.length && days[j]<days[i]+durations[k]){
                    j++;
                }
                dp[i] = Math.min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }

}
